/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class MinimumWindowSubsequence {
	String reString = "";// 不存在，需要返回空字符串而非null
	int minLen = Integer.MAX_VALUE;

	public String minWindow(String S, String T) {
		int n = S.length();
		int m = T.length();
		if (n == 0 || m == 0) {
			return "";
		}
		int[][][] dp = new int[n][m + 1][n];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				for (int j2 = 0; j2 < dp[0][0].length; j2++) {
					dp[i][j][j2] = j == m ? i - j2 : Integer.MAX_VALUE;
				}
			}
		}
		int minLenRec = Integer.MAX_VALUE;
		int minIRec = n;
		for (int i = n - 2; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				char A = S.charAt(i);
				char B = S.charAt(j);
				for (int s = i; s >= 0; s--) {
					if (A == B) {
						dp[i][j][s] = dp[i + 1][j + 1][s];
					} else {
						dp[i][j][s] = dp[i + 1][j][s];
					}
					if (A == T.charAt(0)) {
						dp[i][j][s] = Math.min(dp[i][j][s], dp[i + 1][1][i]);
					}
					if (j == 0) {
						int len = i - s;
						if (minLenRec > len) {
							minLenRec = len;
						} else if (minLenRec == len) {
							if (minIRec > i) {
								minIRec = i;
							}
						}
					}
				}
			}
		}
		System.out.println(minIRec + " " + minLenRec);
		return S.substring(minIRec, minIRec + minLenRec);
	}

	public String minWindow2(String S, String T) {
		helper(S, T, 0, 0, 0);
		return reString;
	}

	private void helper(String s, String t, int i, int j, int start) {
		int n = s.length();
		int m = t.length();
		if (j == m) {
			int len = i - start;
			if (len < minLen) {
				minLen = len;
				reString = s.substring(start, i);
			}
			return;
		}
		if (i == n) {
			return;
		}
		if (s.charAt(i) == t.charAt(j)) {
			helper(s, t, i + 1, j + 1, start);
		} else {
			helper(s, t, i + 1, j, start);
		}
		if (s.charAt(i) == t.charAt(0)) {// 开头晚，长度相同的情况不考虑
			helper(s, t, i + 1, 1, i);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "abcdebdde";
		String T = "bde";
		System.out.println(new MinimumWindowSubsequence().minWindow(S, T));
	}

}
